package com.leetcode.tree.bst;

import com.leetcode.basic.TreeNode;

/**
 * @author Dennis Li
 * @date 2020/8/11 22:39
 */
public class RecoverTree_99 {

    private TreeNode pre, t1, t2;

    public void recoverTree1(TreeNode root) {
        inorder(root);

        final int temp = t1.val;
        t1.val = t2.val;
        t2.val = temp;

    }

    private void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        // 出现这两种情况，可以直接加入root
        if (pre != null && root.val < pre.val) {
            if (t1 == null) t1 = pre;
            // 第二个逆序应该 记录root，不使用else是因为有可能出现恰好是最后两个节点逆序
            t2 = root;
        }
        pre = root;
        inorder(root.right);
    }

    /**
     * Morris 遍历算法
     * 核心：通过设置线索，返回根节点，而不需要进行弹栈确认
     *
     * @param root
     */
    public void recoverTree(TreeNode root) {
        TreeNode before = null;
        TreeNode first = null;
        TreeNode second = null;
        while (root != null) {
            //当左子树不为null，寻找左子树的最右节点，该节点为中序遍历中的前一个节点
            if (root.left != null) {
                TreeNode pre = getPredecessor(root);
                //pre节点没被修改，则修改右节点为root，以便后续循环中能通过pre.right回到root节点
                if (pre.right == null) {
                    pre.right = root;
                    root = root.left;
                    //继续遍历左子树
                    continue;
                } else if (pre.right == root) {
                    //将修改后的pre节点恢复原样
                    pre.right = null;
                }
            }
            //当左子树为null，或者pre.right为root时，先判断before节点和root节点是否倒序，然后再遍历右子树
            if (first == null && before != null && before.val > root.val)
                first = before;
            if (first != null && before != null && before.val > root.val)
                second = root;
            before = root;
            root = root.right;
        }
        swap(first, second);
    }

    //寻找一个节点的左子树的最右节点
    private TreeNode getPredecessor(TreeNode root) {
        TreeNode pre = root;
        if (root.left != null) {
            pre = pre.left;
            while (pre.right != null && pre.right != root) {
                pre = pre.right;
            }
        }
        return pre;
    }

    //交换两个节点
    private void swap(TreeNode first, TreeNode second) {
        if (first != null && second != null) {
            int temp = first.val;
            first.val = second.val;
            second.val = temp;
        }
    }

    private void morrisTraverse(TreeNode root) {
        TreeNode pre = null, first = null, second = null;
        while (root != null) {
            if (root.left != null) {
                final TreeNode node = getMostRight(root);
                if (node.right == null) {
                    node.right = root;
                    // 会一直降低到最左端
                    root = root.left;
                    continue;
                } else if (node.right == root) {
                    // 取消直接建立的指针关系
                    node.right = null;
                }
            }
            // 判断是否产生了逆序
            if (first == null && pre != null && pre.val > root.val)
                first = pre;
            if (second == null && pre != null && pre.val > root.val)
                second = root;
            pre = root;
            root = root.right;
        }
        swap(first, second);
    }

    private TreeNode getMostRight(TreeNode root) {
        if (root.left == null) {
            return root;
        }
        TreeNode node = root.left;
        while (node.right != null && node.right != root) {
            node = node.right;
        }
        return node;
    }

    private void morrisTraverse2(TreeNode root) {
        TreeNode first = null, second = null, pre = null;
        while (root != null) {
            final TreeNode node = getMostRight(root);
            if (node.right == null) {
                node.right = root;
                root = root.left;
                continue;
            } else if (node.right == root) {
                // 复原树，并且会继续向下执行
                node.right = null;
            }
            /*      完成上述遍历后，会降至最左端的最低结点，并且右结点将会是父节点     */

            if (pre != null && first == null && pre.val > root.val) {
                first = pre;
            } else if (pre != null && second == null && pre.val > root.val) {
                second = root;
            }
            pre = root;
            root = root.right;
        }
        swap(first, second);
    }

    private TreeNode getMostRight2(TreeNode root) {
        if (root.left == null) return root;
        TreeNode node = root.left;

        while (node.right != null && node.right != root) {
            node = node.right;
        }

        return node;
    }

    static class Solution {
        public void morrisTraverse(TreeNode root) {
            TreeNode pre = null;
            while (root != null) {
                if (root.left != null) {
                    TreeNode node = getMostRight(root);
                    if (node.right == null) {
                        node.right = root;
                        root = root.left;
                        continue;
                    } else if (node.right == root) {
                        node.right = null;
                    }
                }
                System.out.println(root.val);
                root = root.right;
            }
        }

        private TreeNode getMostRight(TreeNode root) {
            TreeNode cur = root.left;
            while (cur != null && cur.right != root) {
                cur = cur.right;
            }
            return cur;
        }
    }


}
